package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 分割回文串 IV
    static class Solution {
        public boolean checkPartitioning(String s) {
            char[] ch = s.toCharArray();
            int n = ch.length;
            boolean[][] dp = new boolean[n][n];

            // 预处理：判断所有子串是否为回文
            for (int i = n-1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (ch[i] == ch[j]) {
                        if (i == j) {
                            dp[i][j] = true;  // 单字符
                        } else if (i+1 == j) {
                            dp[i][j] = true;  // 相邻字符
                        } else {
                            dp[i][j] = dp[i+1][j-1];  // 看内部
                        }
                    }
                }
            }

            // 枚举分割点：三段为 [0,i-1], [i,j], [j+1,n-1]
            for (int i = 1; i < n-1; i++) {
                for (int j = i; j < n-1; j++) {
                    if (dp[0][i-1] && dp[i][j] && dp[j+1][n-1]) {
                        return true;
                    }
                }
            }

            return false;
        }
    }
}